package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 * 排列不像是组合问题
 * 组合问题是用 startIndex 来去重，startIndex 会控制每一层遍历时选择的节点，随着递归的深入，每一层能选的节点数量越来越少
 * 排列问题每一层选择的节点数量都是相同的，需要借助 used 数组来实现去重
 */

public class Permutations {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> permute(int[] nums) {
            int[] used = new int[nums.length];
            backtracking(nums ,used);
            return res;
        }

        private void backtracking(int[] nums, int[] used){
            if(path.size() == nums.length){
                res.add(new ArrayList<>(path));
                return;
            }

            for(int i = 0; i < nums.length; i++){
                if(used[i] == 1) continue;
                path.add(nums[i]);
                used[i] = 1;
                backtracking(nums, used);
                used[i] = 0;
                path.remove(path.size()-1);
            }
        }
    }
}
